package zigzagLevelOrder

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var res [][]int

func ZigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return res
	}
	res = make([][]int, 0)
	res = append(res, []int{})
	dfs(root, 0)
	for i, v := range res {
		if i%2 == 1 {
			for j, k := 0, len(v)-1; j < k; j, k = j+1, k-1 {
				v[j], v[k] = v[k], v[j]
			}
		}
	}
	return res
}

func dfs(root *TreeNode, level int) {
	if root == nil {
		return
	}
	if len(res) == level {
		res = append(res, []int{})
	}
	res[level] = append(res[level], root.Val)

	dfs(root.Right, level+1)
	dfs(root.Left, level+1)
}
